\documentclass{ctexart}
\usepackage{amsmath}
\usepackage{amssymb}

\title{第四次课堂作业}

\author{邵柯欣\\ 信息与计算科学\\ 3200103310}

\begin{document}

\maketitle

\section{2.9}
$E[X_i] = 20, Var[X_i] = 2, 15 \le X_i \le 22, \bar{X} = \frac{1}{n}\sum X_i$;
\subsection{assume first that n = 20 (the number of random variables).}
$E[\bar{X}] = E[X] = 1, Var[\bar{X}] = \frac{Var[X]}{n} = 0.1$.
\subsubsection{Use the Chebyshev inequality to upper-bound $Pr[\bar{X} > 21]$.}
$Pr[\bar{X} > 21] \le Pr[\bar{X} \ge 21] \le Pr[|\bar{X} - E[\bar{X}]| \ge 20] \le \frac{Var[\bar{X}]}{20^2} = 0.0005$.
\subsubsection{Use the Chernoff-Hoeffding inequality to upper-bound $Pr[\bar{X} > 21]$.}
$Pr[\bar{X} > 21] \le Pr[|\bar{X} - E[\bar{X}]| > 20] \le 2*e^{\frac{-2*20*20*20}{7*7}}$.
\subsection{assume first that n = 200 (the number of random variables).}
$E[\bar{X}] = E[X] = 0.1, Var[\bar{X}] = \frac{Var[X]}{n} = 0.01$.
\subsubsection{Use the Chebyshev inequality to upper-bound $Pr[\bar{X} > 21]$.}
$Pr[\bar{X} > 21] \le Pr[\bar{X} \ge 21] \le Pr[|\bar{X} - E[\bar{X}]| \ge 20.9] \le \frac{Var[\bar{X}]}{200^2} = \dfrac{1}{4*10^6}$.
\subsubsection{Use the Chernoff-Hoeffding inequality to upper-bound $Pr[\bar{X} > 21]$.}
$Pr[\bar{X} > 21] \le Pr[|\bar{X} - E[\bar{X}]| > 20.9] \le 2*e^{\frac{-2*20.9*20.9*200}{7*7}}$
\section{2.10}
5 items $a_1, a_2, a_3, a_4, a_5$ with weights $w_1 = 2, w_2 = 3, w_3 = 10, w_4 = 8, w_5 = 1$. We know upper bounds on the weights with $w_1 \in [0, 4], w_2 \in [0, 4], w_3 \in [0, 10], w_4 \in [0, 10], w_5 \in [0, 2]$.
\subsection{In the context of importance sampling, list the importance $\psi_i$ for each item.}
$\psi_1 = 4, \psi_2 = 4, \psi_3 = 10, \psi_4 = 10, \psi_5 = 2$.\\

\subsection{Use the Partition of Unity approach to sample 2 items
  accroding to their importance. Use $u_1 = 0.377 and u_2 = 0.852$ as
  the ``random'' values in unif(0, 1].}
$w_I = \dfrac{\dfrac{\Psi}{n*\psi_3}*w_3 + \dfrac{\Psi}{n*\psi_4}*w_4}{2} = 5.4$\\

\subsection{Report the estimate of the average weight using importance sampling, based on the two items sampled.}
Thus $\bar{\Psi} = \frac{\sum \psi_i}{n} = 6$.

\end{document}